package com.cb2.algorithm.leetcode;

import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * <a href='https://leetcode.cn/problems/maximum-sum-of-almost-unique-subarray'>几乎唯一子数组的最大和(Maximum Sum of Almost Unique Subarray)</a>
 * <p>给你一个整数数组 nums 和两个正整数 m 和 k 。</p>
 * <p>请你返回 nums 中长度为 k 的 几乎唯一 子数组的 最大和 ，如果不存在几乎唯一子数组，请你返回 0 。</p>
 * <p>如果 nums 的一个子数组有至少 m 个互不相同的元素，我们称它是 几乎唯一 子数组。</p>
 * <p>子数组指的是一个数组中一段连续 非空 的元素序列。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 *  示例 1：
 *      输入：nums = [2,6,7,3,1,7], m = 3, k = 4
 *      输出：18
 *      解释：总共有 3 个长度为 k = 4 的几乎唯一子数组。分别为 [2, 6, 7, 3] ，[6, 7, 3, 1] 和 [7, 3, 1, 7] 。这些子数组中，和最大的是 [2, 6, 7, 3] ，和为 18 。
 *
 * 示例 2：
 *      输入：nums = [5,9,9,2,4,5,4], m = 1, k = 3
 *      输出：23
 *      解释：总共有 5 个长度为 k = 3 的几乎唯一子数组。分别为 [5, 9, 9] ，[9, 9, 2] ，[9, 2, 4] ，[2, 4, 5] 和 [4, 5, 4] 。这些子数组中，和最大的是 [5, 9, 9] ，和为 23 。
 *
 * 示例 3：
 *      输入：nums = [1,2,1,2,1,2,1], m = 3, k = 3
 *      输出：0
 *      解释：输入数组中不存在长度为 k = 3 的子数组含有至少  m = 3 个互不相同元素的子数组。所以不存在几乎唯一子数组，最大和为 0 。
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>1 <= nums.length <= 2 * 10^4</li>
 *     <li>1 <= m <= k <= nums.length</li>
 *     <li>1 <= nums[i] <= 10^9</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2025/4/30 14:09
 */
public class LC2841MaximumSumOfAlmostUniqueSubarray_M {
    static class Solution {
        public long maxSum(List<Integer> nums, int m, int k) {
            Map<Integer, Integer> cntMap = new HashMap<>();
            long sum = 0;
            for (int i = 0; i < k; i++) {
                Integer val = nums.get(i);
                cntMap.put(val, cntMap.getOrDefault(val, 0) + 1);
                sum += nums.get(i);
            }
            long res = cntMap.size() >= m ? sum : 0;
            for (int i = k; i < nums.size(); i++) {
                int source = nums.get(i - k);
                if (cntMap.get(source) == 1) {
                    cntMap.remove(source);
                } else {
                    cntMap.put(source, cntMap.get(source) - 1);
                }
                sum -= source;

                Integer target = nums.get(i);
                cntMap.put(target, cntMap.getOrDefault(target, 0) + 1);
                sum += target;

                if (cntMap.size() >= m) {
                    res = Math.max(res, sum);
                }
            }
            return res;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.maxSum(Arrays.asList(2, 6, 7, 3, 1, 7), 3, 4));
        System.out.println(solution.maxSum(Arrays.asList(5, 9, 9, 2, 4, 5, 4), 1, 3));
        System.out.println(solution.maxSum(Arrays.asList(1, 2, 1, 2, 1, 2, 1), 3, 3));
        System.out.println(solution.maxSum(Arrays.asList(
                        996021492, 996021492, 973489433, 66259330, 554129007, 713784351,
                        646092981, 328987029, 469368828, 685679486, 66259330, 165954500,
                        731567840, 595800464, 552439059, 14673238, 157622945, 521321042,
                        386913607, 733723177, 330475939, 462727944, 69696035, 958945846,
                        648914457, 627088742, 363551051, 50748590, 400980660, 674779765,
                        439950964, 613843311, 385212079, 725525766, 813504429, 385212079,
                        66563232, 578031878, 935017574, 554725813, 456892672, 245308625,
                        626768145, 270964388, 554725813, 768296675, 676923124, 939689721,
                        115905765, 625193590, 717796816, 27972217, 277242430, 768296675,
                        480860474, 659230631, 570682291, 601689140, 955632265, 767424000,
                        251696645, 675750691, 767424000, 251696645, 767424000, 675750691,
                        675750691, 251696645),
                8, 8));
    }
}
